// N皇后问题 (递归实现)
// 测试链接 : https://leetcode.cn/problems/n-queens-ii/
public class NQueens1 {

    public int totalNQueens(int n) {
        return func(0, new int[n], n);
    }

    //i表示第几行
    //path表示记录可以放皇后的位置 如果 i表示行， 则path[i] 表示列
    public int func(int i, int[] path, int n){
        if(i == n){
            return 1;  //表示i已经走完了这个表，存在一个摆放皇后的方法
        }

        int ans = 0;  //记录答案
        //遍历每个列
        for(int j = 0; j < n; j++){
            if(check(path, i, j)){
                path[i] = j;
                ans += func(i + 1, path, n);
            }
        }

        return ans;
    }

    //判断当前行i 和 当前列 j是否合法
    public boolean check(int[] path, int i , int j){
        for(int k = 0; k < i; k++){ //遍历从第0行到i-1行，看看摆放的位置符不符合要求
            if(j == path[k] || Math.abs(i-k) == Math.abs(j - path[k])) {
                return false;
            }
        }
        return true;
    }
}
